/*================================================================
*   Copyright (C) 2019 Guangzhou Firefly Ltd. All rights reserved.
*   
*   文件名称：yh_triangle.c
*   创 建 者：luhuadong
*   创建日期：2019年10月15日
*   描    述：输入 n 值，使用递归函数，求杨辉三角形中各个位置上的值
*
================================================================*/


#include <stdio.h>
#include <time.h>

typedef unsigned int uint;


/* 返回第i行第j列的值 */
static uint yhtriangle(uint i, uint j)
{
	if(j > i)  return 0;  /* 第i行有且只有i个值 */
	if(j == 1) return 1;  /* 每行第一个值都是1 */
	if(j == i) return 1;  /* 每行最后一个值也是1 */
	
	/* 每个数等于它上方两数之和 */
	return (yhtriangle(i-1, j-1) + yhtriangle(i-1, j));
}

int main(void)
{
	uint n, i, j, run_time;
	clock_t begin, end;

	printf(">> ");
	scanf("%u", &n);
	printf("\n");

	begin = clock();

	/* 输出杨辉三角 */
	for(i=2; i<=n; i++) {

		for(j=1; j<=i; j++) {

			printf("%u ", yhtriangle(i, j));
		}
		printf("\n");
	}
	end = clock();

	/* 统计算法执行时间 */
	run_time = (end - begin) * 1000.0 / CLOCKS_PER_SEC * 1000;
	printf("\ntime=%uus\n", run_time);

	return 0;
}
